import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Set;

public class Solution886 {

    class UnionUtil{
        private HashMap<Integer,Integer> util;
        private int count;
        UnionUtil(){
            util = new HashMap<>();
            count = 0;
        }

        int getCount(){
            return count;
        }

        int find(int element){
            if(util.containsKey(element) == false){
                util.put(element, element);
                count++;
            }
            if(util.get(element) != element){
                util.put(element, find(util.get(element)));
            }
            return util.get(element);
        }

        boolean union(int x, int y){
            int rootX = find(x);
            int rootY = find(y);
            if(rootX == rootY){
                return false;
            }
            util.put(rootX, rootY);
            count--;
            return true;
        }
    }

    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<Integer>[] dislikeList = new List[n + 1];
        for(int i = 1; i <= n; i++) {
            dislikeList[i] = new ArrayList<>();
        }
        for (int[] dislike : dislikes) {
            dislikeList[dislike[0]].add(dislike[1]);
            dislikeList[dislike[1]].add(dislike[0]);
        }
        UnionUtil union = new UnionUtil();
        for(int tmpNum = 1; tmpNum <= n; tmpNum++) {
            List<Integer> tmpDislike = dislikeList[tmpNum];
            if(!tmpDislike.isEmpty()){
                Integer firstDislike = tmpDislike.get(0);
                for (Integer dislikeNum : tmpDislike) {
                    union.union(firstDislike, dislikeNum);
                }
                if(union.find(firstDislike) == union.find(tmpNum)){
                    return false;
                }
            }
        }
        return true;
    }
}
